package com.arron.algorithm.leetcodetop100.二分查找;

public class 寻找两个正序数组的中位数 {




    public double findMedianSortedArrays_plus_plus(int[] nums1, int[] nums2) {


        int m = nums1.length;
        int n = nums2.length;


        if ((m+n)%2 ==0 ){
            double k1 = k_min(nums1,0,m-1,nums2,0,n-1,(m+n)/2);
            double k2 = k_min(nums1,0,m-1,nums2,0,n-1,(m+n)/2+1);
            return (k1+k2)/2;
        }else {

            return k_min(nums1,0,m-1,nums2,0,n-1,(m+n)/2+1);
        }


    }



    // 寻找num1，nums2数组排序后的中第k小的数
    public double k_min(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){

        int len1 = end1-start1+1;
        int len2 = end2-start2+1;


        if (len1>len2){
            return k_min(nums2,start2,end2,nums1,start1,end1,k);
        }
        if (len1 == 0){
            return nums2[start2+k-1];
        }

        if (k==1){
            return Math.min(nums1[start1],nums2[start2]);
        }

        // 防止 k/2 > 数组的长度
        int i  = start1 + Math.min(len1,k/2)-1;
        int j  = start2 + Math.min(len2,k/2)-1;

        if (nums1[i] > nums2[j]){
            return k_min(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }


        return k_min(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
    }





    /**
     *  使用变量 记录中位数就行，省去额外数组的空间复杂度
     *  时间复杂度  O((len1+len2)/2)
     *  空间复杂度 O(1)
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays_plus(int[] nums1, int[] nums2) {


        int pre = -1;
        int cur = 0;

        int len  = nums1.length + nums2.length;
        int i1 = 0;
        int i2 = 0;

        for (int i = 0; i <= len/2; i++) {

            pre = cur;


            if (i1 == nums1.length ){
                cur = nums2[i2];
                i2++;
                continue;
            }
            if (i2 == nums2.length ){
                cur = nums1[i1];
                i1++;
                continue;
            }

            if (nums1[i1] < nums2[i2]){
                cur = nums1[i1];
                i1++;
            }else {
                cur = nums2[i2];
                i2++;
            }

        }

        if (len %2 == 0){
            return (double)(pre+cur)/2;
        }


        return cur;

    }









    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int[] temp = new int[nums1.length+nums2.length];
        int i = 0,j=0,k=0;
        for (; i <nums1.length && j<nums2.length ;) {
            if (nums1[i] < nums2[j]){
                temp[k++] = nums1[i];
                i++;
            }else {
                temp[k++] = nums2[j];
                j++;
            }
        }
        if (i == nums1.length){
            for (int z = j; z < nums2.length; z++) {
                temp[k++] = nums2[z];
            }
        }else if (j== nums2.length){
            for (int z = i; z < nums1.length; z++) {
                temp[k++] = nums1[z];
            }
        }
        if (temp.length %2 ==0){
            int i1 = temp.length/2;
            int i2= temp.length/2-1;
            return ((double) temp[i1]+(double) temp[i2])/2;

        }
        return temp[temp.length/2];
    }

    public static void main(String[] args) {
        寻找两个正序数组的中位数 mid = new 寻找两个正序数组的中位数();
        int[] nums1 = {1,2,3};
        int[] nums2 = {1,4,5,6};
        System.out.println(mid.findMedianSortedArrays_plus(nums1, nums2));
    }

}

